package algorithm.math;

/**
 * leetcode : https://leetcode.com/problems/ugly-number-ii/description/
 * Difficulty : Medium
 *
 * 由第一题已经知道了 uglyNumber 的定义，该题要求找出第N个 uglyNumber （1也算 uglyNumber）
 *
 * 由丑数定义可以知道
 * uglyNumber 序列，可以由 2 3 5 乘以之前已经生成的uglyNumber 来递推生成，问题是需要有序
 *
 * 可以假设 uglyNumber 序列为numArr numArr[0]=1
 * 那么由 2 3 5 相乘之前丑数得到的序列，我们称为 L2，L3，L5
 * 那么令  i2 i3 i5 为相乘的之前丑数的索引值
 * 则有：
 * n2 = 2 * numArr[i2]
 * n3 = 3 * numArr[i3]
 * n5 = 5 * numArr[i5]
 *
 * 那只要比较 n2 n3 n5 哪个最小，就是下一个丑数。
 * 取了哪个列表的数，哪个列表的index就自增1
 * 例如，n2最小，那么i2++, 得到下一个uglyNumber 在下次比较时候，再和其他的比较大小。
 *
 * @Author Antony
 * @Since 2018/7/18 16:36
 */
public class UglyNumberII {

    public static void main(String[] args) {
        int n = 1;
        System.out.println(nthUglyNumber(n));
    }

    /**
     * beats 93.85% - 4ms
     */
    public static int nthUglyNumber(int n) {
        int[] numArr = new int[n];
        numArr[0] = 1;
        int numSize = 1;
        int i2=0, i3=0, i5=0;   // 丑数序列索引
        int n2,n3,n5;           // 丑数序列当前计算的值
        int currNum;
        while(numSize < n){
            n2 = numArr[i2] *2;
            n3 = numArr[i3] *3;
            n5 = numArr[i5] *5;
            currNum = Math.min(n2, Math.min(n3,n5));
            if(currNum == n2) i2++;
            if(currNum == n3) i3++;
            if(currNum == n5) i5++;
            numArr[numSize] = currNum;
            numSize++;
        }

        return numArr[n-1];
    }
}
